題目

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

題意

從陣列中找出和為0的三個元素，並組成陣列，不能有兩個內容一樣的陣列。

測試範圍：
0 <= 陣列長度 <= 3000
-10000 <= 元素值 <= 10000

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

解題步驟

先篩選掉陣列長度<3以及最小值大於0的情況：

let len = nums.length;
if (len < 3 || Math.min(...nums) > 0) {
    return [];
}

題目有規定，不能有內容一樣的陣列，所以先將陣列由小到大排序再處理：

nums.sort((x, y) => x - y);

為找出和為0的3個元素，我們先假設有3個index分別為i,j,k

let sum = nums[i] + nums[j] + nums[k];

先固定i，移動j,k縮小範圍搜尋，
若sum>0，k須左移，才有可能sum=0。
若sum<0，j須右移，才有可能sum=0。
若sum=0，j右移，k左移，繼續尋找下一組。
當j>=k時，表示這次的搜尋已結束：

以下情況會產生內容一樣的陣列：
[-2, 0, 0, 2, 2]

如何解決？
當j或k的下一個值與現在的一樣時，就跳過，不計算：

while (nums[j] == nums[j + 1]) j++;
while (nums[k] == nums[k - 1]) k--;

Solution

var threeSum = function (nums) {
   let len = nums.length;
   if (len < 3 || Math.min(...nums) > 0) {
       return [];
   }
   let ary = [];
   nums.sort((x, y) => x - y);
   for (let i = 0; i < len - 2; i++) {
       let j = i + 1;
       let k = len - 1;
       while (j < k) {
           let sum = nums[i] + nums[j] + nums[k];
           if (sum === 0) {
               ary.push([nums[i], nums[j], nums[k]]);
                while (nums[j] == nums[j + 1]) j++;
                while (nums[k] == nums[k - 1]) k--;
                k--;
                j++;
            } else if (sum > 0) {
                k--;
            } else if (sum < 0) {
                j++;
            }
       }
   }
   return ary;
};